package com.kyrie.lib_sys.utils.learn.leetCode;

import java.util.*;

/**
 * 力扣----哈希篇
 *
 * @author heefM
 * @date 2025-07-26
 */
public class LeetCode_Hash {

    public static void main(String[] args) {


        int arr[] = {1, 2, 3};
        System.out.println(Arrays.toString(twoSum(arr, 3)));
        System.out.println("_______________________________________________________________________");

        String[] strs = {"acb", "bca", "cba", "def", "efg", "efd"};
        System.out.println((groupAnagrams(strs)));
        System.out.println("_______________________________________________________________________");


        int arr2[] = {1, 2, 4, 3, 4, 7, -1, 0};
        System.out.println(longestConsecutive(arr2));

    }

    /**
     * 两数之和(hash)   一个数组里面的数字和为target
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {

            int diff = target - nums[i];//将两个值的相加转成,目标值减去里面的一个值得到一个差值(再判断数组里面存在这个差值吗)
            if (map.containsKey(diff)) { //存在就返回这个差值的下标和一开始被减去的值的下标(i)
                return new int[]{map.get(diff), i}; //返回对应的下标()   为什么get(diff就可以获取下标)   [1,2,3]  map里面存在(key=1:value=0) (2:1) (3:2)
                                                    // 因为每一次循环都把当前值存进map里面了,所以map里面有这个值,就可以返回这个值对应的下标 get(3)就会返回2

            }
            map.put(nums[i], i);//每次循环都把当前值存进map里面,方便后面判断

        }
        return null;
    }

    /**
     * 字母异位词分组 (hash)  每一组字母里面的多个字母都是相同的,但是不同的字母顺序
     *
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        //思路就是获取里面的一组字母, 然后给他排序,  使用排序过后的字母组当作map里面的key,  value 就是一个list用来存放顺序不同的字母组
        HashMap<String, List<String>> map = new HashMap<>();
        for (String key : strs) {
            char[] chars = key.toCharArray();//将获取的字母组转换成char数组
            Arrays.sort(chars); //排序 (类似bac --->abc)
            String sortKey = new String(chars);//组装排序后的字母组

            if (map.containsKey(sortKey)) { //如果map中存在这个key，则将key对应的value添加到list中
                List<String> list = map.get(sortKey);
                list.add(key);
            } else {
                ArrayList<String> list = new ArrayList<>(); //如果不存在, 就表示当前是新的字母组,我们给他分配一个新的list存放,而key就是排序的key
                list.add(key);
                map.put(sortKey, list);
            }
        }
        return new ArrayList<>(map.values());//返回map的value(是一个list集合)
    }


    /**
     * 最长连续序列(hash)  给一个数组，求最长的连续序列的长度(求最长的一个)
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {

        // 使用set 做去重处理
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int count = 0;  //记录当前最长的连续序列的长度
        int result = 0; //记录结果()
        for (Integer num : set) {
            //判断当前是连续序列的第一个数字  (当前数字前面没有数字  相差为1;   比如5 减一)
            if (!set.contains(num - 1)) {
                count = 1;
                int curr = num;//记录当前数字(一组连续最长的开始数字)

                while (set.contains(curr + 1)) {   //判断set中是否存在下一个数字是不是连续序列的数字
                    count++;  //存在 当前长度+1
                    curr++;   //当前记录的数也+1
                }
                result = Math.max(result, count); //比较当前最长的与历史存的最长的比较, 取最大值
            }
        }
        return result;
    }

}
